import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution2045 {
    public int secondMinimum(int n, int[][] edges, int time, int change) {
        int[] first=new int[n+1];
        Arrays.fill(first,-1);
        int[] next=new int[edges.length*2+1];
        int[] go=new int[edges.length*2+1];
        Arrays.fill(next,-1);
        int count=0;
        for (int[] edge : edges) {
            go[count]=edge[1];
            next[count]=first[edge[0]];
            first[edge[0]]=count;
            count++;
            go[count]=edge[0];
            next[count]=first[edge[1]];
            first[edge[1]]=count;
            count++;
        }
        int[][] f=new int[2][n+1];
        Arrays.fill(f[0],Integer.MAX_VALUE);
        Arrays.fill(f[1],Integer.MAX_VALUE);
        f[0][1]=0;
        Queue<int[]> queue=new LinkedList<>();
        queue.offer(new int[]{1,0});
        while (!queue.isEmpty()){
            int[] t=queue.poll();
            int p=first[t[0]];
            while (p!=-1){
                int v=go[p];
                if (f[0][v]>t[1]+1){
                    f[0][v]=t[1]+1;
                    queue.offer(new int[]{v,t[1]+1});
                }else if (f[0][v]<t[1]+1 && f[1][v]>t[1]+1){
                    f[1][v]=t[1]+1;
                    queue.offer(new int[]{v,t[1]+1});
                }
                p=next[p];
            }
        }
        return cal(f[1][n],time,change);
    }


    int cal(int k,int time,int change){
        int ans=0;
        for (int i=0;i<k;i++){
            if (ans/change%2==0){
                ans=ans+time;
            }else{
                ans=(ans/change+1)*change+time;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution2045().secondMinimum(5,new int[][]{{1,2},{1,3},{1,4},{3,4},{4,5}},3,5));
    }
}
